// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
)

func CheckHeight(real []int) int {
	//计数排序
	bucket := make([]int, 100, 100)
	for _, item := range real {
		bucket[item-1] += 1
	}
	sorted := make([]int, 0, len(real))
	for index := range bucket {
		flag := bucket[index]
		for i := 0; i < flag; i++ {
			sorted = append(sorted, index+1)
		}
	}

	//统计
	ret := 0
	for index := range real {
		if sorted[index] != real[index] {
			ret = ret + 1
		}
	}
	return ret
}

func main() {
	array := []int{1, 6, 8, 1, 6, 6}
	res := CheckHeight(array)
	fmt.Println(res)
}

//$ go run interview6-12.go
//4
